DC/LC analysis of Keccak-f[200]
Linear cryptanalysis

1 trails of length 2 read and checked.
1 trails of length 3 read and checked.
1 trails of length 4 read and checked.
Minimum weight: 8
       1 trails of weight  8
       1 trails of weight 20
       1 trails of weight 46

Showing the trails up to weight 46 (in no particular order).

2-round linear trail of total weight 8
* Profile related to χ:
Propagation weights:    4   4
Active rows:            2   2
* Profile related to θ:
Gaps:      9   0
Kernel:    N   k
Previous round would have weight at least 80
Round 0 (weight 4) after previous χ, then before θ of gap 9, then before χ (2 active rows):
X...X   .X...   ...X.   ..X..   XX..X   XX.XX   X...X   XXXX.  |  .X...   ....X   ..XX.   X.X..   XX..X   XXX..   .X.X.   XXX.X  |  .....     .....    
..XXX   XXXX.   ...XX   X.XX.   .X.X.   ....X   .X..X   X.X..  |  .X...   ....X   ..XX.   X.X..   XX..X   XXX..   .X.X.   XXX.X  |  .....     .....    
X.X..   X....   XXXXX   .XX..   XX..X   .XX..   .X.X.   ..X.X  |  .XX..   ....X   ..XX.   X.X..   XX..X   XXX..   .X.X.   XXX.X  |  ..X.. z^3 ..... z^3
XX...   .....   ..XX.   X..XX   XX.XX   ..X.X   X..XX   ..X.X  |  .X...   ....X   ..XX.   X.X..   XX..X   XXX..   .X.X.   XXX.X  |  .....     .....    
X.X.X   ..XX.   ..X..   XXXX.   .X..X   .X...   X..X.   .XXX.  |  .X...   ....X   ..XX.   X.X..   XX.XX   XXX..   .X.X.   XXX.X  |  .....     ...X.    
                                                                  -OO--   ----O   --OO-   O-O--   OO-OO   OOO--   -O-O-   OOO-O
Round 1 (weight 4) after previous χ, then before θ of gap 0, then before χ (2 active rows):
.....     .....      |  .....      |  .....    
.....     .....      |  ..X..      |  ..X..    
..X.. z^3 ..... z^3  |  ..X.. z^7  |  ..X.. z^7
.....     .....      |  .....      |  .....    
.....     ...X.      |  .....      |  .....    
                        -----    

3-round linear trail of total weight 20
* Profile related to χ:
Propagation weights:    8   8   4
Active rows:            4   4   2
* Profile related to θ:
Gaps:     10   0   0
Kernel:    N   k   k
Previous round would have weight at least 82
Round 0 (weight 8) after previous χ, then before θ of gap 10, then before χ (4 active rows):
.X..X   X....   .XXXX   .XXX.   .X.XX   X.X.X   X..X.   ..X.X  |  ..X.X   XXXX.   ..XX.   X.X..   X..XX   .X..X   XXXXX   X....  |      ..X..    .....   .....
..X..   XX.XX   .XXX.   XXX.X   .X..X   .XXXX   X...X   X.X..  |  ..X.X   XXXX.   ..XX.   X....   X..XX   .X..X   XXXXX   .....  |      .....    .....   X....
X.XXX   X.X.X   ..XX.   XX..X   XX...   ...X.   X.XX.   .X..X  |  ..X.X   XXXX.   ..XX.   X....   X..XX   .X..X   X.XXX   X....  |  z^3 ..... zz .X...   .....
.X.XX   X....   X.XX.   XXXX.   .XX.X   ...XX   .XX..   X....  |  ..X.X   XXXX.   ..XX.   X....   X..XX   .X..X   XXXXX   X...X  |      .....    .....   ....X
..X.X   .X...   ...X.   XX..X   XXXXX   X..X.   .X.XX   XX...  |  ..X.X   XXXX.   ..XX.   X....   X..XX   .X..X   XXXXX   X....  |      .....    .....   .....
                                                                  --O-O   OOOO-   --OO-   O-O--   O--OO   -O--O   O-OOO   ----O
Round 1 (weight 8) after previous χ, then before θ of gap 0, then before χ (4 active rows):
    ..X..    .....   .....  |  .X...   .....      |  .X...   .....    
    .....    .....   X....  |  .....   .....      |  .....   .....    
z^3 ..... zz .X...   .....  |  ..+.. z ...X. z^5  |  ..+.. z ...X. z^5
    .....    .....   ....X  |  .X...   .....      |  .X...   .....    
    .....    .....   .....  |  .....   ...X.      |  .....   ...X.    
                               -----   -----    
Round 2 (weight 4) after previous χ, then before θ of gap 0, then before χ (2 active rows):
.X...   .....      |      .....    |      .....  
.....   .....      |      ..XX.    |      ..XX.  
..+.. z ...X. z^5  |  z^6 ..... z  |  z^6 ..... z
.X...   .....      |      ..XX.    |      ..XX.  
.....   ...X.      |      .....    |      .....  
                          -----  

4-round linear trail of total weight 46
* Profile related to χ:
Propagation weights:   16   4   4  22
Active rows:            8   2   2  10
* Profile related to θ:
Gaps:      6   1   0   2
Kernel:    N   N   k   N
Previous round would have weight at least 68
Round 0 (weight 16) after previous χ, then before θ of gap 6, then before χ (8 active rows):
...XX   ...X.   ...XX   X.X..   X....   ..X.X   ....X   .....  |  .X...   X....   ...XX   .X..X   XX.XX   X....   ..XX.   X....  |  .....    .....   .....   ...X.   X....
.XXX.   XXX.X   .....   .....   ...X.   ..X..   .....   XX.X.  |  .X...   X....   ...XX   .X.XX   XX.XX   X....   ..X..   .....  |  .....    ...X.   .....   .....   .....
..+X.   XX...   XX...   .....   X....   ....X   XXXXX   ...XX  |  .X+..   X....   ...XX   .X...   XX.XX   XX...   ..X..   .....  |  ..+.. zz ....X z .X...   .....   .....
..XX.   .....   ..X.X   ...XX   .X.X.   .....   .X...   X...X  |  .X...   X....   ...XX   .X..X   XX.XX   X....   .....   .....  |  .....    .....   .....   ..X..   .....
..X.X   XX...   X..X.   X.X..   .X..X   .X...   ..X.X   ..X..  |  .....   X....   ...XX   .X..X   XX.XX   X....   ..X..   X....  |  .X...    .....   .....   .....   X....
                                                                  -----   O----   ---OO   -O-O-   OO-OO   OO---   ---O-   -----
Round 1 (weight 4) after previous χ, then before θ of gap 1, then before χ (2 active rows):
.....    .....   .....   ...X.   X....  |  ....X     .X...  |  .....     .....
.....    ...X.   .....   .....   .....  |  ....X     .X...  |  .....     .....
..+.. zz ....X z .X...   .....   .....  |  ..+.X z^6 .....  |  ..+.. z^6 .X...
.....    .....   .....   ..X.X   .....  |  X....     .X...  |  X...X     .....
.X...    .....   .....   .....   X....  |  ....X     .X...  |  .....     .....
                                           O----     -----
Round 2 (weight 4) after previous χ, then before θ of gap 0, then before χ (2 active rows):
.....     .....  |    .X...      |    .X...    
.....     .....  |    .....      |    .....    
..+.. z^6 .X...  |  z ..... z^6  |  z ..... z^6
....X     .....  |    .X...      |    .X...    
.....     .....  |    .....      |    .....    
                      -----    
Round 3 (weight 22) after previous χ, then before θ of gap 2, then before χ (10 active rows):
  .X...      |      .....  |      ...XX   .XX..
  .....      |      .....  |      ...XX   .XX..
z ..... z^6  |  z^7 .....  |  z^6 ...XX   .XX..
  .X...      |      ..XX.  |      ...XX   .X.X.
  .....      |      .....  |      ...XX   .XX..
                    --OO-

